public class BinarySearchTree {

    static class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
    }

        public TreeNode root;
        public void insert(int key){
            if(root==null){
                root=new TreeNode(key) ;
                return;
            }
                TreeNode parent=null;
                TreeNode cur=root;
                TreeNode node=new TreeNode(key) ;
                while(cur!=null){
                    if(key<cur.val){
                        parent=cur;
                        cur=cur.left;
                    }else if(key>cur.val){
                        parent=cur;
                        cur=cur.right;
                    }else{
                        return;//不能插入两个相同的数据
                    }
                }
                    if(key<parent.val){
                        parent.left=node;
                    }else{
                        parent.right=node;
                    }
            }
    
        public TreeNode search(int key){
            TreeNode cur=root;
            while(cur!=null){
                if(key==cur.val) {
                    return cur;
                } else if (key<cur.val) {
                    cur=cur.left;
                }else{
                    cur=cur.right;
                }
            }
            return null;
        }


    public void remove(int key){
        TreeNode parent=null;
        TreeNode cur=root;
        while(cur!=null){
            if(key<cur.val) {
                parent=cur;
                cur=cur.left;
            }else if (key>cur.val) {
                parent=cur;
                cur=cur.right;
            }else{
                removeNode(parent,cur);//删除该处节点
                return;
            }
        }
    }
    private void removeNode(TreeNode parent,TreeNode cur) {
        if(cur.left==null){
            if(cur==root){
                root=cur.right;
            }else if(parent.left==cur){
                parent.left = cur.right;
            }else{
                parent.right = cur.right;
            }
        }else if(cur.right==null){
            if(cur==root){
                root=cur.left;
            }else if(parent.left==cur){
                parent.left = cur.left;
            }else{
                parent.right = cur.left;
            }
        }else{
            TreeNode targetparent=cur;
            TreeNode target=cur.right;
            while(target.left!=null){
                targetparent=target;
                target=target.left;
            }
            cur.val=target.val;
            if(targetparent.left==target){
                targetparent.left=target.right;
            }else{
                targetparent.right=target.right;
            }
        }
    }
}

